﻿// 1312. 让字符串成为回文串的最少插入次数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;
/*
https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/


给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。

示例 1：
输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。

示例 2：
输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

示例 3：
输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。

提示：
1 <= s.length <= 500
s 中所有字符都是小写字母。
*/


class Solution {
public:
    vector<vector<int>> dp;
    int minInsertions(string s) {
        dp.resize(510,vector<int>(510,0x3f3f3f3f));
        for (int i = 0; i < 510; i++) dp[i][i] = 0;
        for (int i = 0; i < s.size()-1; i++) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = 0;
            }
            else {
                dp[i][i + 1] = 1;
            }
        }
        
        for (int len = 3; len <= s.size(); len++) {
            for (int i = 0; i+len-1 < s.size(); i++) {
                int j = i + len - 1;
                if (s[i] == s[j]) {
                    dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
                }
                else {
                    dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + 2);
                }
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
                dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1);
            }
        }

        cout << dp[0][s.size()-1] << endl;

        return dp[0][s.size()-1];
    }
};



int main()
{
    Solution s;


    s.minInsertions("leetcode");
}
 